CF547C Mike and Foam

cic_iii 毫升泡沫的酒在架子上的瓶数,A=maxi=1naiA=\max_{i=1}^n a_i

为了方便将二元组视为有序,答案除以 22 即可。

i=1Aj=1Acicj[gcd(i,j)=1]\sum_{i=1}^A \sum_{j=1}^A c_i c_j [\gcd(i,j)=1]

d=1Aμ(d)i=1A/dj=1A/dcidcjd\sum_{d=1}^A \mu(d) \sum_{i=1}^{A/d} \sum_{j=1}^{A/d} c_{id} c_{jd}

d=1Aμ(d)(i=1A/dcid)2\sum_{d=1}^A \mu(d) ( \sum_{i=1}^{A/d}c_{id} )^2

{Δ+=daiμ(d)((i=1A/dcid+1)2(i=1A/dcid)2)Δ=daiμ(d)((i=1A/dcid)2(i=1A/dcid1)2)\begin{cases} \Delta_+=\sum_{d|a_i} \mu(d) ((\sum_{i=1}^{A/d}c_{id}+1)^2-(\sum_{i=1}^{A/d}c_{id})^2) \\ \Delta_-=\sum_{d|a_i} \mu(d) ((\sum_{i=1}^{A/d}c_{id})^2-(\sum_{i=1}^{A/d}c_{id}-1)^2) \end{cases}

{Δ+=daiμ(d)(2i=1A/dcid+1)Δ=daiμ(d)(2i=1A/dcid1)\begin{cases} \Delta_+=\sum_{d|a_i} \mu(d) (2\sum_{i=1}^{A/d}c_{id}+1) \\ \Delta_-=\sum_{d|a_i} \mu(d) (2\sum_{i=1}^{A/d}c_{id}-1) \end{cases}

如果有多个 11 上面的式子就 GG 了,不过这也很好处理,直接将答案减去/加上 11 的个数即可。

时间复杂度 O(n+qn)\mathcal O(n+q\sqrt n)

#include <cstdio>
#define LL long long

const int MAXN = 5e5;

int prnum , prime[ MAXN + 5 ] , mu[ MAXN + 5 ];
bool vis[ MAXN + 5 ];
void sieve( ) {
	mu[ 1 ] = 1;
	for( int i = 2 ; i <= MAXN ; i ++ ) {
		if( !vis[ i ] ) prime[ ++ prnum ] = i , mu[ i ] = -1;
		for( int j = 1 ; j <= prnum && 1ll * i * prime[ j ] <= MAXN ; j ++ ) {
			vis[ i * prime[ j ] ] = 1;
			if( i % prime[ j ] == 0 ) break;
			mu[ i * prime[ j ] ] = -mu[ i ];
		}
	}
}

int n , q , a[ MAXN + 5 ] , c[ MAXN + 5 ];
LL Ans;
bool on[ MAXN + 5 ];

LL Calc[ MAXN + 5 ];
// int Calc( int d ) {
// 	int tmp = 0;
// 	for( int i = d ; i <= MAXN ; i += d ) tmp += c[ i ];
// 	return tmp;
// }
void Add( int x ) {
	for( int d = 1 ; d * d <= x ; d ++ )
		if( x % d == 0 ) {
			Ans += mu[ d ] * ( 2 * Calc[ d ] + 1 ) , Calc[ d ] ++;
			if( d * d != x ) Ans += mu[ x / d ] * ( 2 * Calc[ x / d ] + 1 ) , Calc[ x / d ] ++;
		}
	c[ x ] ++;
	if( x == 1 ) Ans --;
}
void Del( int x ) {
	for( int d = 1 ; d * d <= x ; d ++ )
		if( x % d == 0 ) {
			Ans -= mu[ d ] * ( 2 * Calc[ d ] - 1 ) , Calc[ d ] --;
			if( d * d != x ) Ans -= mu[ x / d ] * ( 2 * Calc[ x / d ] - 1 ) , Calc[ x / d ] --;
		}
	c[ x ] --;
	if( x == 1 ) Ans ++;
}

int main( ) {
	sieve();
	scanf("%d %d",&n,&q);
	for( int i = 1 ; i <= n ; i ++ ) scanf("%d",&a[ i ]);
	for( int i = 1 , pos ; i <= q ; i ++ ) {
		scanf("%d",&pos);
		on[ pos ] ? Del( a[ pos ] ) : Add( a[ pos ] );
		on[ pos ] ^= 1;
		printf("%lld\n", Ans / 2 );
	}
	return 0;
}